/*-------------------------------------------------------------------------
 *
 * gist_private.h
 *	  GiST 的私有声明 -- 与 GiST 的内部实现相关的声明，
 *	  而不是公共 API
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * src/include/access/gist_private.h
 *
 *-------------------------------------------------------------------------
 */
#ifndef GIST_PRIVATE_H
#define GIST_PRIVATE_H

#include "access/amapi.h"
#include "access/gist.h"
#include "access/itup.h"
#include "lib/pairingheap.h"
#include "storage/bufmgr.h"
#include "storage/buffile.h"
#include "utils/hsearch.h"
#include "access/genam.h"

/*
 * 一次操作中页面可以被分割成的“半部”的最大数量。
 * 通常一次分裂产生 2 个半部，但如果键的长度非常
 * 不同，或者在一次操作中插入多个键时（如
 * 插入指向内部节点的下行链接），可以更多。对此没有理论
 * 限制，但在实践中，如果你在一次分裂中得到超过一 handful 的页面半部，
 * 那就意味着 opclass 实现有问题。
 * GIST_MAX_SPLIT_PAGES 是一个任意限制，用于设置在分裂期间
 * 使用的一些本地数组的大小。请注意，同时可以保持锁定的
 * 缓冲区数量也有限制，MAX_SIMUL_LWLOCKS，
 * 所以如果你将其提高到超过该限制，你只会得到不同的
 * 错误。
 */
#define GIST_MAX_SPLIT_PAGES		75

/* 缓冲区锁模式 */
#define GIST_SHARE	BUFFER_LOCK_SHARE
#define GIST_EXCLUSIVE	BUFFER_LOCK_EXCLUSIVE
#define GIST_UNLOCK BUFFER_LOCK_UNLOCK

typedef struct
{
	BlockNumber prev;
	uint32		freespace;
	char		tupledata[FLEXIBLE_ARRAY_MEMBER];
} GISTNodeBufferPage;

#define BUFFER_PAGE_DATA_OFFSET MAXALIGN(offsetof(GISTNodeBufferPage, tupledata))
/* 返回节点缓冲区页面中的空闲空间 */
#define PAGE_FREE_SPACE(nbp) (nbp->freespace)
/* 检查节点缓冲区页面是否为空 */
#define PAGE_IS_EMPTY(nbp) (nbp->freespace == BLCKSZ - BUFFER_PAGE_DATA_OFFSET)
/* 检查节点缓冲区页面是否没有足够的空间用于索引元组 */
#define PAGE_NO_SPACE(nbp, itup) (PAGE_FREE_SPACE(nbp) < \
										MAXALIGN(IndexTupleSize(itup)))

/*
 * GISTSTATE：进行任何 GiST 索引操作所需的信息
 *
 * 此结构保存索引的 opclass 特定支持
 * 函数的调用信息（按索引列），以及索引的元组描述符。
 *
 * scanCxt 保存 GISTSTATE 本身以及在索引操作生命周期内存在的任何数据。
 * 我们通过 fn_mcxt 将其传递给支持函数，
 * 以便它们可以在其中存储扫描生命周期数据。该
 * 函数在 tempCxt 中调用，通常是短生命周期的
 * （即，在每个元组后重置）。然而，如果我们不拘一格
 * 地进行每个元组上下文的重置，tempCxt 可以与 scanCxt 相同。
 */
typedef struct GISTSTATE
{
	MemoryContext scanCxt;		/* 扫描生命周期数据的上下文 */
	MemoryContext tempCxt;		/* 短期调用函数的上下文 */

	TupleDesc	leafTupdesc;	/* 索引的元组描述符 */
	TupleDesc	nonLeafTupdesc; /* 非叶子页面的截断元组描述符 */
	TupleDesc	fetchTupdesc;	/* 在索引唯一扫描中返回的元组描述符 */

	FmgrInfo	consistentFn[INDEX_MAX_KEYS];
	FmgrInfo	unionFn[INDEX_MAX_KEYS];
	FmgrInfo	compressFn[INDEX_MAX_KEYS];
	FmgrInfo	decompressFn[INDEX_MAX_KEYS];
	FmgrInfo	penaltyFn[INDEX_MAX_KEYS];
	FmgrInfo	picksplitFn[INDEX_MAX_KEYS];
	FmgrInfo	equalFn[INDEX_MAX_KEYS];
	FmgrInfo	distanceFn[INDEX_MAX_KEYS];
	FmgrInfo	fetchFn[INDEX_MAX_KEYS];

	/* 传递给支持函数的排序规则 */
	Oid			supportCollation[INDEX_MAX_KEYS];
} GISTSTATE;


/*
 * 在 GiST 索引搜索过程中，我们必须维护一个未访问项的队列，
 * 这些项可以是单个堆元组或整个索引页面。如果
 * 是有序搜索，则未访问的项应按距离顺序访问。
 * 同样距离的未访问项应按深度优先顺序访问，
 * 即先是堆项，然后是较低的索引页面，再然后是
 * 较高的索引页面；这个规则避免了在由于 LIMIT
 * 而提前结束的搜索中做额外的工作。
 *
 * 为了执行有序搜索，我们使用配对堆来管理
 * 距离顺序队列。在非有序搜索中（没有 order-by 操作符），
 * 我们使用它在未访问的索引页面之前返回堆元组，
 * 以确保深度优先顺序，但所有条目在其他方面被认为是
 * 相等的。
 */

/* 待访问的单个堆元组 */
typedef struct GISTSearchHeapItem
{
	ItemPointerData heapPtr;
	bool		recheck;		/* 如果必须重新检查 quals，则为 T */
	bool		recheckDistances;	/* 如果必须重新检查距离，则为 T */
	HeapTuple	recontup;		/* 从索引重构的数据，用于
 * 索引唯一扫描 */
	OffsetNumber offnum;		/* 跟踪页面中的偏移以标记元组为
								 * LP_DEAD */
} GISTSearchHeapItem;

/* 未访问项，可能是索引页面或堆元组 */
typedef struct GISTSearchItem
{
	pairingheap_node phNode;
	BlockNumber blkno;			/* 索引页面编号，或无效块编号 */
	union
	{
		GistNSN		parentlsn;	/* 父页面的LSN，如果是索引页面 */
		/* 我们必须存储parentlsn以检测是否发生了分裂 */
		GISTSearchHeapItem heap;	/* 堆信息，如果是堆元组 */
	}			data;

	/* numberOfOrderBys条目 */
	IndexOrderByDistance distances[FLEXIBLE_ARRAY_MEMBER];
} GISTSearchItem;

#define GISTSearchItemIsHeap(item)	((item).blkno == InvalidBlockNumber)

#define SizeOfGISTSearchItem(n_distances) \
	(offsetof(GISTSearchItem, distances) + \
	 sizeof(IndexOrderByDistance) * (n_distances))

/*
 * GISTScanOpaqueData: GiST索引扫描的私有状态
 */
typedef struct GISTScanOpaqueData
{
	GISTSTATE  *giststate;		/* 索引信息，见上文 */
	Oid		   *orderByTypes;	/* ORDER BY表达式的数据类型 */

	pairingheap *queue;			/* 未访问项的队列 */
	MemoryContext queueCxt;		/* 持有队列的上下文 */
	bool		qual_ok;		/* 如果条件永远无法满足，则为false */
	bool		firstCall;		/* 在第一次gistgettuple调用之前为true */

	/* 预分配的工作区数组 */
	IndexOrderByDistance *distances;	/* gistindex_keytest的输出区域 */

	/* 被删除项的信息，如果有的话 (killedItems 为 NULL 如果从未使用) */
	OffsetNumber *killedItems;	/* 被删除项的偏移量 */
	int			numKilled;		/* 当前存储项的数量 */
	BlockNumber curBlkno;		/* 当前块的数量 */
	GistNSN		curPageLSN;		/* 页被读取时在WAL流中的位置 */

	/* 在非有序搜索中，可返回的堆项存储在这里： */
	GISTSearchHeapItem pageData[BLCKSZ / sizeof(IndexTupleData)];
	OffsetNumber nPageData;		/* 数组中有效项的数量 */
	OffsetNumber curPageData;	/* 下一个要返回的项 */
	MemoryContext pageDataCxt;	/* 持有获取的元组的上下文，用于
								 * 仅索引扫描 */
} GISTScanOpaqueData;

typedef GISTScanOpaqueData *GISTScanOpaque;

/* 尽管名字如此，gistxlogPage 并不是任何 xlog 记录的一部分 */
typedef struct gistxlogPage
{
	BlockNumber blkno;
	int			num;			/* 后续索引元组的数量 */
} gistxlogPage;

/* SplitedPageLayout - gistSplit函数结果 */
typedef struct SplitedPageLayout
{
	gistxlogPage block;
	IndexTupleData *list;
	int			lenlist;
	IndexTuple	itup;			/* 页的联合键 */
	Page		page;			/* 操作 */
	Buffer		buffer;			/* 在所有过程后写入 */

	struct SplitedPageLayout *next;
} SplitedPageLayout;

/*
 * GISTInsertStack用于在插入期间锁定缓冲区和传递参数
 */
typedef struct GISTInsertStack
{
	/* 当前页面 */
	BlockNumber blkno;
	Buffer		buffer;
	Page		page;

	/*
	 * 从page->lsn的日志序列号，以识别页面更新并与页面的nsn进行比较，以识别页面分裂
	 */
	GistNSN		lsn;

	/*
	 * 如果设置了，我们在向下寻找插入目标时会拆分页面。这意味着我们需要从父级重试，
	 * 因为此页面的下行链接可能不再覆盖新键。
	 */
	bool		retry_from_parent;

	/* 指向此页面的父页面中的下行链接偏移 */
	OffsetNumber downlinkoffnum;

	/* 指向父级的指针 */
	struct GISTInsertStack *parent;
} GISTInsertStack;

/* gistsplit.c中多列分割逻辑的工作状态和结果 */
typedef struct GistSplitVector
{
	GIST_SPLITVEC splitVector;	/* 传递给/传出用户PickSplit方法 */

	Datum		spl_lattr[INDEX_MAX_KEYS];	/* 在
											 * splitVector.spl_left中的子键的并集 */
	bool		spl_lisnull[INDEX_MAX_KEYS];

	Datum		spl_rattr[INDEX_MAX_KEYS];	/* 在
											 * splitVector.spl_right中的子键的并集 */
	bool		spl_risnull[INDEX_MAX_KEYS];

	bool	   *spl_dontcare;	/* 标记可以进入分裂任一侧的元组，且零损失 */
} GistSplitVector;

typedef struct
{
	Relation	r;
	Relation	heapRel;
	Size		freespace;		/* 要保留的自由空间 */
	bool		is_build;

	GISTInsertStack *stack;
} GISTInsertState;

/* GiST索引的根页面 */
#define GIST_ROOT_BLKNO				0

/*
 * 在PostgreSQL 9.1之前，我们依赖于所谓的“无效元组”在内部页面上
 * 来完成不完整页面分裂的崩溃恢复。如果在页面分裂中发生崩溃，
 * 以至于下行指针尚未插入，崩溃恢复将插入一个特殊的下行指针。
 * 无效元组的语义是如果你在扫描中遇到一个，它必须始终被跟随，
 * 因为我们不知道子页面上的元组是否匹配。
 *
 * 我们不再创建这样的无效元组，现在我们用F_FOLLOW_RIGHT标记
 * 这样不完整分裂的左半部分，并在下次需要在该页面上插入时正确完成分裂。
 * 为了保持磁盘上的兼容性以便于pg_upgrade，我们仍然将所有内部元组的
 * 偏移数量存储为0xffff。如果在插入过程中遇到带有0xfffe的无效元组，
 * 我们将抛出错误，尽管扫描仍然可以处理它们。如果你pg_upgrade一个预9.1
 * 的GiST索引，而它已经因为崩溃而包含无效元组，你应该只会遇到无效元组。
 * 这应该是罕见的，如果你的索引中有任何无效元组，建议你进行REINDEX，
 * 因此抛出错误是我们对此的支持的极限。
 */
#define TUPLE_IS_VALID		0xffff
#define TUPLE_IS_INVALID	0xfffe

#define  GistTupleIsInvalid(itup)	( ItemPointerGetOffsetNumber( &((itup)->t_tid) ) == TUPLE_IS_INVALID )
#define  GistTupleSetValid(itup)	ItemPointerSetOffsetNumber( &((itup)->t_tid), TUPLE_IS_VALID )




/*
 * 附加到内部节点的缓冲区，在以缓冲模式构建索引时使用。
 */
typedef struct
{
	BlockNumber nodeBlocknum;	/* 此缓冲区所针对的索引块# */
	int32		blocksCount;	/* 当前被缓冲区占用的块数# */

	BlockNumber pageBlocknum;	/* 临时文件块 # */
	GISTNodeBufferPage *pageBuffer; /* 内存中的缓冲区页面 */

	/* 这个缓冲区是否已排队待清空？ */
	bool		queuedForEmptying;

	/* 这是临时副本吗，不在哈希表中？ */
	bool		isTemp;

	int			level;			/* 0 == 叶子节点 */
} GISTNodeBuffer;

/*
 * 指定级别是否有缓冲区？（注意参数的多次评估。）
 */
#define LEVEL_HAS_BUFFERS(nlevel, gfbb) \
	((nlevel) != 0 && (nlevel) % (gfbb)->levelStep == 0 && \
	 (nlevel) != (gfbb)->rootlevel)

/* 指定的缓冲区是否至少填充一半（应该排队等待清空）？ */
#define BUFFER_HALF_FILLED(nodeBuffer, gfbb) \
	((nodeBuffer)->blocksCount > (gfbb)->pagesPerBuffer / 2)

/*
 * 指定的缓冲区是否已满？我们的缓冲区实际上可以无限增长，
 * 超过“最大”大小，因此这仅意味着缓冲区是否已经超出
 * 名义最大大小。
 */
#define BUFFER_OVERFLOWED(nodeBuffer, gfbb) \
	((nodeBuffer)->blocksCount > (gfbb)->pagesPerBuffer)

/*
 * 关于构建缓冲区的一般信息的数据结构。
 */
typedef struct GISTBuildBuffers
{
	/* 缓冲区和元数据的持久内存上下文。 */
	MemoryContext context;

	BufFile    *pfile;			/* 用于存储缓冲区的临时文件 */
	long		nFileBlocks;	/* 临时文件的当前大小 */

	/*
	 * 可调整大小的空闲块数组。
	 */
	long	   *freeBlocks;
	int			nFreeBlocks;	/* 数组中当前空闲块的数量 */
	int			freeBlocksLen;	/* 数组当前分配的长度 */

	/* 按块号散列的缓冲区 */
	HTAB	   *nodeBuffersTab;

	/* 排定待清空的缓冲区列表 */
	List	   *bufferEmptyingQueue;

	/*
	 * 缓冲构建算法的参数。levelStep 确定树中哪些
	 * 级别有缓冲区，而 pagesPerBuffer 确定每个缓冲区的
	 * 大小。
	 */
	int			levelStep;
	int			pagesPerBuffer;

	/* 每个级别的缓冲区列表数组，供最终清空使用 */
	List	  **buffersOnLevels;
	int			buffersOnLevelsLen;

	/*
	 * 动态大小的缓冲区数组，当前其最后一个页面
	 * 已加载到主内存中。
	 */
	GISTNodeBuffer **loadedBuffers;
	int			loadedBuffersCount; /* loadedBuffers 中条目的数量 */
	int			loadedBuffersLen;	/* 加载缓冲区的分配大小 */

	/* 当前根节点的级别（= 索引树的高度 - 1） */
	int			rootlevel;
} GISTBuildBuffers;

/* GiSTOptions->buffering_mode 值 */
typedef enum GistOptBufferingMode
{
	GIST_OPTION_BUFFERING_AUTO,
	GIST_OPTION_BUFFERING_ON,
	GIST_OPTION_BUFFERING_OFF
} GistOptBufferingMode;

/*
 * GiST 的 reloptions 的存储类型
 */
typedef struct GiSTOptions
{
	int32		vl_len_;		/* varlena 头部（请勿直接触摸！） */
	int			fillfactor;		/* 页面填充因子百分比（0..100） */
	GistOptBufferingMode buffering_mode;	/* 缓冲构建模式 */
} GiSTOptions;

/* gist.c */
extern void gistbuildempty(Relation index);
extern bool gistinsert(Relation r, Datum *values, bool *isnull,
					   ItemPointer ht_ctid, Relation heapRel,
					   IndexUniqueCheck checkUnique,
					   bool indexUnchanged,
					   struct IndexInfo *indexInfo);
extern MemoryContext createTempGistContext(void);
extern GISTSTATE *initGISTstate(Relation index);
extern void freeGISTstate(GISTSTATE *giststate);
extern void gistdoinsert(Relation r,
						 IndexTuple itup,
						 Size freespace,
						 GISTSTATE *giststate,
						 Relation heapRel,
						 bool is_build);

/* 从 gistplacetopage() 中返回的列表在 *splitinfo 中 */
typedef struct
{
	Buffer		buf;			/* 分裂页面的 "一半" */
	IndexTuple	downlink;		/* 此半部分的下链。 */
} GISTPageSplitInfo;

extern bool gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate,
							Buffer buffer,
							IndexTuple *itup, int ntup,
							OffsetNumber oldoffnum, BlockNumber *newblkno,
							Buffer leftchildbuf,
							List **splitinfo,
							bool markfollowright,
							Relation heapRel,
							bool is_build);

extern SplitedPageLayout *gistSplit(Relation r, Page page, IndexTuple *itup,
									int len, GISTSTATE *giststate);

/* gistxlog.c */
extern XLogRecPtr gistXLogPageDelete(Buffer buffer,
									 FullTransactionId xid, Buffer parentBuffer,
									 OffsetNumber downlinkOffset);

extern void gistXLogPageReuse(Relation rel, BlockNumber blkno,
							  FullTransactionId latestRemovedXid);

extern XLogRecPtr gistXLogUpdate(Buffer buffer,
								 OffsetNumber *todelete, int ntodelete,
								 IndexTuple *itup, int ntup,
								 Buffer leftchild);

extern XLogRecPtr gistXLogDelete(Buffer buffer, OffsetNumber *todelete,
								 int ntodelete, TransactionId latestRemovedXid);

extern XLogRecPtr gistXLogSplit(bool page_is_leaf,
								SplitedPageLayout *dist,
								BlockNumber origrlink, GistNSN oldnsn,
								Buffer leftchild, bool markfollowright);

extern XLogRecPtr gistXLogAssignLSN(void);

/* gistget.c */
extern bool gistgettuple(IndexScanDesc scan, ScanDirection dir);
extern int64 gistgetbitmap(IndexScanDesc scan, TIDBitmap *tbm);
extern bool gistcanreturn(Relation index, int attno);

/* gistvalidate.c */
extern bool gistvalidate(Oid opclassoid);
extern void gistadjustmembers(Oid opfamilyoid,
							  Oid opclassoid,
							  List *operators,
							  List *functions);

/* gistutil.c */

#define GiSTPageSize   \
	( BLCKSZ - SizeOfPageHeaderData - MAXALIGN(sizeof(GISTPageOpaqueData)) )

#define GIST_MIN_FILLFACTOR			10
#define GIST_DEFAULT_FILLFACTOR		90

extern bytea *gistoptions(Datum reloptions, bool validate);
extern bool gistproperty(Oid index_oid, int attno,
						 IndexAMProperty prop, const char *propname,
						 bool *res, bool *isnull);
extern bool gistfitpage(IndexTuple *itvec, int len);
extern bool gistnospace(Page page, IndexTuple *itvec, int len, OffsetNumber todelete, Size freespace);
extern void gistcheckpage(Relation rel, Buffer buf);
extern Buffer gistNewBuffer(Relation r);
extern bool gistPageRecyclable(Page page);
extern void gistfillbuffer(Page page, IndexTuple *itup, int len,
						   OffsetNumber off);
extern IndexTuple *gistextractpage(Page page, int *len /* 输出 */ );
extern IndexTuple *gistjoinvector(IndexTuple *itvec, int *len,
								  IndexTuple *additvec, int addlen);
extern IndexTupleData *gistfillitupvec(IndexTuple *vec, int veclen, int *memlen);

extern IndexTuple gistunion(Relation r, IndexTuple *itvec,
							int len, GISTSTATE *giststate);
extern IndexTuple gistgetadjusted(Relation r,
								  IndexTuple oldtup,
								  IndexTuple addtup,
								  GISTSTATE *giststate);
extern IndexTuple gistFormTuple(GISTSTATE *giststate,
								Relation r, Datum *attdata, bool *isnull, bool isleaf);
extern void gistCompressValues(GISTSTATE *giststate, Relation r,
							   Datum *attdata, bool *isnull, bool isleaf, Datum *compatt);

extern OffsetNumber gistchoose(Relation r, Page p,
							   IndexTuple it,
							   GISTSTATE *giststate);

extern void GISTInitBuffer(Buffer b, uint32 f);
extern void gistinitpage(Page page, uint32 f);
extern void gistdentryinit(GISTSTATE *giststate, int nkey, GISTENTRY *e,
						   Datum k, Relation r, Page pg, OffsetNumber o,
						   bool l, bool isNull);

extern float gistpenalty(GISTSTATE *giststate, int attno,
						 GISTENTRY *key1, bool isNull1,
						 GISTENTRY *key2, bool isNull2);
extern void gistMakeUnionItVec(GISTSTATE *giststate, IndexTuple *itvec, int len,
							   Datum *attr, bool *isnull);
extern bool gistKeyIsEQ(GISTSTATE *giststate, int attno, Datum a, Datum b);
extern void gistDeCompressAtt(GISTSTATE *giststate, Relation r, IndexTuple tuple, Page p,
							  OffsetNumber o, GISTENTRY *attdata, bool *isnull);
extern HeapTuple gistFetchTuple(GISTSTATE *giststate, Relation r,
								IndexTuple tuple);
extern void gistMakeUnionKey(GISTSTATE *giststate, int attno,
							 GISTENTRY *entry1, bool isnull1,
							 GISTENTRY *entry2, bool isnull2,
							 Datum *dst, bool *dstisnull);

extern XLogRecPtr gistGetFakeLSN(Relation rel);

/* gistvacuum.c */
extern IndexBulkDeleteResult *gistbulkdelete(IndexVacuumInfo *info,
											 IndexBulkDeleteResult *stats,
											 IndexBulkDeleteCallback callback,
											 void *callback_state);
extern IndexBulkDeleteResult *gistvacuumcleanup(IndexVacuumInfo *info,
												IndexBulkDeleteResult *stats);

/* gistsplit.c */
extern void gistSplitByKey(Relation r, Page page, IndexTuple *itup,
						   int len, GISTSTATE *giststate,
						   GistSplitVector *v,
						   int attno);

/* gistbuild.c */
extern IndexBuildResult *gistbuild(Relation heap, Relation index,
								   struct IndexInfo *indexInfo);
extern void gistValidateBufferingOption(const char *value);

/* gistbuildbuffers.c */
extern GISTBuildBuffers *gistInitBuildBuffers(int pagesPerBuffer, int levelStep,
											  int maxLevel);
extern GISTNodeBuffer *gistGetNodeBuffer(GISTBuildBuffers *gfbb,
										 GISTSTATE *giststate,
										 BlockNumber blkno, int level);
extern void gistPushItupToNodeBuffer(GISTBuildBuffers *gfbb,
									 GISTNodeBuffer *nodeBuffer, IndexTuple item);
extern bool gistPopItupFromNodeBuffer(GISTBuildBuffers *gfbb,
									  GISTNodeBuffer *nodeBuffer, IndexTuple *item);
extern void gistFreeBuildBuffers(GISTBuildBuffers *gfbb);
extern void gistRelocateBuildBuffersOnSplit(GISTBuildBuffers *gfbb,
											GISTSTATE *giststate, Relation r,
											int level, Buffer buffer,
											List *splitinfo);
extern void gistUnloadNodeBuffers(GISTBuildBuffers *gfbb);

#endif							/* GIST_PRIVATE_H */
